// 为运算表达式设计优先级

package Leetcode;

import java.util.ArrayList;
import java.util.List;

// 使用回溯无法去重
class Solution_241_1 {
    public List<Integer> result = new ArrayList<>();

    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> value = new ArrayList<>();
        List<Character> operator = new ArrayList<>();
        int sum = 0;
        for (int i = 0; i < expression.length(); i++) {
            if (i + 1 == expression.length()) {
                sum = sum * 10 + (expression.charAt(i) - '0');
                value.add(sum);
                sum = 0;
            } else if (expression.charAt(i) == '+' || expression.charAt(i) == '-' || expression.charAt(i) == '*') {
                value.add(sum);
                sum = 0;
                operator.add(expression.charAt(i));
            } else {
                sum = sum * 10 + (expression.charAt(i) - '0');
            }
        }
        // value.forEach(i -> System.out.println(i));
        // System.out.println("-----------------------------");
        // operator.forEach(i -> System.out.println(i));

        backtrack(value, operator);
        return result;
    }

    public void backtrack(List<Integer> value, List<Character> operator) {
        if (value.size() == 1) {
            result.add(value.get(0));
            return;
        }

        for (int i = 0; i < operator.size(); i++) {
            int a = value.get(i);
            int b = value.get(i + 1);
            value.remove(i);
            value.remove(i);
            if (operator.get(i) == '+')
                value.add(i, a + b);
            else if (operator.get(i) == '-')
                value.add(i, a - b);
            else
                value.add(i, a * b);
            char c = operator.get(i);
            operator.remove(i);
            backtrack(value, operator);
            // 回溯
            value.remove(i);
            value.add(i, b);
            value.add(i, a);
            operator.add(i, c);
        }
    }
}

class Solution_241_2 {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> result = new ArrayList<>();
        // 遍历整个表达式，寻找第一个运算符
        int len = expression.length();
        int i = 0;
        for (i = 0; i < len; i++) {
            if (Character.isDigit(expression.charAt(i)))
                continue;
            else
                break;
        }

        // 如果没有运算符,那么整个表达式为一个数字
        if (i == len)
            result.add(Integer.parseInt(expression));
        // 如果存在运算符，则把表达式分为 左部分 和 右部分 进行递归操作
        for (; i < len; i++) {
            if (Character.isDigit(expression.charAt(i)))
                continue;
            char operator = expression.charAt(i);
            // 递归调用本函数获取左部分和右部分的所有组合
            List<Integer> left = new ArrayList<>(diffWaysToCompute(expression.substring(0, i)));
            List<Integer> right = new ArrayList<>(diffWaysToCompute(expression.substring(i + 1, len)));
            // 合并左右两个部分
            for (int l : left)
                for (int r : right) {
                    if (operator == '+')
                        result.add(l + r);
                    else if (operator == '-')
                        result.add(l - r);
                    else
                        result.add(l * r);
                }
        }// for-i

        return result;
    }
}